133. 克隆图

Similar Question

Solution Tips

方案一: Bfs

  var cloneGraph = function (node) {
    if (node == null) return null
    const map = {}
    const cloneNode = new Node(node.val, [])
    map[node.val] = cloneNode
    // shift & push
    const queue = [node]
    while (queue.length > 0) {
      const cur = queue.shift()
      
      for (let i = 0; i < cur.neighbors.length; i++) {
        const n = cur.neighbors[i]
		// 第一次遍历到该节点, 做复制和入队列
        if (!map.hasOwnProperty(n.val)) {
          map[n.val] = new Node(n.val, [])
          queue.push(n)
        }
		// 之前可能已经复制过了, 都是孩子, 直接入列即可
        map[cur.val].neighbors.push(map[n.val])
      }
    }
    return cloneNode
  }

方案二: Dfs

  function clone(node,map={}) {
    const cloneNode = new Node(node.val)
    map[node.val] = cloneNode
    cloneNode.neighbors = node.neighbors.map((neighbor)=>{
      if(neighbor.val in map) return map[neighbor.val]
      return clone(neighbor,map)
    })
    return cloneNode
  }
  var cloneGraph = function(node) {
    return clone(node)
  }